# 206
#Definition for singly-linked list.
#class ListNode:
#def __init__(self, val=0, next=None):
#self.val = val
#self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None  #如果head是None ，也可以返回prev
        cur = head
        while cur :
            next = cur.next  #记录下一个节点
            cur.next = prev  # 关键步骤
            prev = cur
            cur = next       # 遍历链表
        return prev

#206
#Definition for singly-linked list.
#class ListNode:
#def __init__(self, val=0, next=None):
#self.val = val
#self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if (not head or not head.next) :
            return head
        new = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new

'''
双链表
#Definition for singly-linked list.
#class ListNode:
#def __init__(self, val=0, next=None, last=None):
#self.val = val
#self.next = next
#self.last = last
'''
class Solution:
    def reverseDoubleList(self, head: ListNode) -> ListNode:
        prev = None  #如果head是None ，也可以返回prev
        cur = head
        while cur :
            next = cur.next  #记录下一个节点
            cur.next = prev  # 关键步骤
            cur.last = next  # 关键步骤
            prev = cur
            cur = next      # 遍历链表
        return prev
#203. 移除链表元素
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        #先看看头部要删多少，因为删除头于其他节点逻辑不通
        while head :
            if head.val != val: break
            head = head.next
        cur = pre = head #此时head.val ！= val 因为前面都删除了
        while cur:
            if cur.val == val:
                pre.next = cur.next
            else:
                pre = cur
            cur = cur.next
        return head

#使用哨兵节点解法
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        new = ListNode(0, head)
        pre = new
        cur = new.next
        while cur:
            if cur.val == val:
                pre.next = cur.next
            else:
                pre = cur  #pre 永远指向上一个不等于val的节点
            cur = cur.next
        return new.next


#02.04. 分割链表

#Definition for singly-linked list.
#class ListNode:
#def init(self, x):
#self.val = x
#self.next = None
#双指针法
class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        prev = head
        curr = head
        while curr :
            if curr.val < x :
                prev.val, curr.val = curr.val, prev.val
                prev = prev.next
            curr = curr.next
        return head

# 876 链表的中间结点
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
'''
当链表节点是偶数时，right指向第二个中间节点，当奇数时，指向中点节点
'''
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        first = sec = head
        while sec and sec.next :
            first = first.next
            sec = sec.next.next
        return first

'''
当链表节点是偶数时，right指向第二个中间节点，当奇数时，指向中点节点后面的那一个
'''
    def middleNode2(self, head: ListNode) -> ListNode:
        if head == None or head.next == None :
			return head
        first = head.next
        sec = head
        while sec.next != None and sec.next.next != None:
			first = first.next    
			sec = sec.next.next
'''
当链表节点是偶数时，right指向第一个中间节点，当奇数时，指向中点节点
'''
    def middleNode3(self, head: ListNode) -> ListNode:
        if head == None or head.next == None :
			return head
        first = sec = head
        while sec.next != None and sec.next.next != None:
			first = first.next    
			sec = sec.next.next

#19
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        slow = ListNode(0, head)  #哨兵
        fast = slow.next  # head
        for _ in range(n) :
            fast = fast.next
        if not fast :
            return head.next  #删除头节点
        while fast :
            fast, slow = fast.next, slow.next
        slow.next = slow.next.next
        return head
#21
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        head = ListNode(None, None)
        new = head
        while list1 and list2 :
            if list1.val <= list2.val :
                new.next, list1 = list1, list1.next
            else :
                new.next, list2 = list2, list2.next
            new = new.next
        if list1 :
            new.next = list1
        else :
            new.next = list2
        return head.next

'''
234. 回文链表
'''
#   need n extra space
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution: 
    def isPalindrome(self, head: ListNode) -> bool:
        cur = head
        stack = []
        while cur != None:
            stack.append(cur)
            cur = cur.next
        while head != None:
            if head.val != stack.pop().val:
                return False
            head = head.next
        return True

#   need n/2 extra space
    def isPalindrome(self, head: ListNode) -> bool:
        if head == None or head.next == None:
            return True
        right = head.next
        cur = head
        while cur.next and cur.next.next :
            right = right.next
            cur = cur.next.next 
        stack = []
        while right :
            stack.append(right)
            right = right.next
        while len(stack) > 0 :
            if head.val != stack.pop().val :
                return False
            head = head.next
        return True

#   O(n) 时间复杂度和 O(1) 空间复杂度
    def isPalindrome(self, head: ListNode) -> bool:
        if head == None or head.next == None:
            return True
        n1 = head  #n1 -> mid
        n2 = head  # n2 -> end
        while n2.next and n2.next.next: # find mid node
            n1 = n1.next  #n1 -> mid    （n1此时是奇数中间节点，或者偶数中间节点的第一个节点）
            n2 = n2.next.next # n2 -> end
        n2 = n1.next; # n2 -> right part first node (当链表节点是偶数时，n2指向第二个中间节点，当奇数时，指向中点后面那个)
        n1.next = None # mid.next -> None   （n1此时时中间节点，或者中间节点的第一个节点）
        n3 = None # 记住next
        while n2 : # right part convert    n2: cur
            n3 = n2.next  # n3 -> save next node
            n2.next = n1  # next of right node convert   n1: pre(这句很关键)
            n1 = n2       # n1 move
            n2 = n3       # n2 move
        n3 = n1     # n3 -> save last node  最后一个节点 n3.next = None
        n2 = head   # n2 -> left first node
        res = True
        while n1 and n2 : # check palindrome
            if n1.val != n2.val:
                res = False
                break
            n1 = n1.next        # left to mid
            n2 = n2.next        #right to mid
        n1 = n3.next
        n3.next = None
        while n1 : # recover list
            n2 = n1.next
            n1.next = n3
            n3 = n1
            n1 = n2
        return res


'''
    将单向链表按某值划分成左边小、中间相等、右边大的形式 【题目】 给定一个单向链表的头节点head，节点的值类型是整型，再给定一个 整数pivot。
实现一个调整链表的函数，将链表调整为左部分都是值小于 pivot 的节点，中间部分都是值等于pivot的节点，右部分都是值大于 pivot的节点。 
除这个要求外，对调整后的节点顺序没有更多的要求。 例如：链表9->0->4->5- >1，pivot=3。 
调整后链表可以是1->0->4->9->5，也可以是0->1->9->5->4。总 之，满 足左部分都是小于3的节点，中间部分都是等于3的节点（本例中这个部 分为空），
右部分都是大于3的节点即可。对某部分内部的节点顺序不做 要求。 
    进阶： 在原问题的要求之上再增加如下两个要求。
在左、中、右三个部分的内部也做顺序要求，要求每部分里的节点从左 到右的 顺序与原链表中节点的先后次序一致。 
例如：链表9->0->4->5->1，pivot=3。 调整后的链表是0->1->9->4->5。 在满足原问题要求的同时，左部分节点从左到 右为0、1。
在原链表中也 是先出现0，后出现1；中间部分在本例中为空，不再 讨论；右部分节点 从左到右为9、4、5。在原链表中也是先出现9，然后出现4， 
最后出现5。 
    如果链表长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。
'''
# 下面这个解法不能保证相对位置
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        if not head : return head
        cur = head
        node_arr = []
        while cur:
            node_arr.append(cur)
            cur = cur.next
        self.arrPartition(node_arr, x)
        for i in range(len(node_arr)-1):
            node_arr[i].next = node_arr[i+1]
        node_arr[len(node_arr)-1].next = None
        return node_arr[0]

    def arrPartition(self, node_arr: ListNode, x: int):
        small = -1
        big = len(node_arr)
        index = 0
        while index != big :
            if node_arr[index].val < x :
                small += 1
                node_arr[index], node_arr[small] = node_arr[small], node_arr[index]
                index += 1
            elif node_arr[index].val == x :
                index += 1
            else :
                big -= 1
                node_arr[index], node_arr[big] = node_arr[big], node_arr[index]

# 下列函数可以实现 如果链表长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)  保留两个分区中每个节点的初始相对位置
    def partition(self, head: ListNode, x: int) -> ListNode:
        sH = None   #  small head
        sT = None   #  small tail
        eH = None   #  equal head
        eT = None   #  equal tail
        bH = None   #  big head
        bT = None   #  big tail
        next = None #save next node
        # every node distributed to three lists
        while head:
            next = head.next
            head.next = None
            if head.val < x :
                if sH == None:
                    sH = head
                    sT = head
                else :
            	    sT.next = head
            	    sT = head
            elif head.val == x :
                if eH == None :
                    eH = head
                    eT = head
                else :
                    eT.next = head
                    eT = head
            else :
                if bH == None :
                    bH = head
                    bT = head
                else :
                    bT.next = head
                    bT = head
            head = next
        # small and equal reconnect
        if sT :
            sT.next = eH
            eT = sT if not eT else eT
        # all reconnect
        if eT :
            eT.next = bH
        return sH if sH else eH if eH else bH

'''
86. 分隔链表   保留两个分区中每个节点的初始相对位置
'''
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        sH = None   #  small head
        sT = None   #  small tail
        bH = None   #  big head
        bT = None   #  big tail
        next = None #save next node
        # every node distributed to three lists
        while head:
            next = head.next
            head.next = None
            if head.val < x :
                if sH == None:
                    sH = head
                    sT = head
                else :
            	    sT.next = head
            	    sT = head
            else :
                if bH == None:
                    bH = head
                    bT = head
                else :
                    bT.next = head
                    bT = head
            head = next
        # small and equal reconnect
        if sT :
            sT.next = bH
            bT = sT if not bT else bT
        return sH if sH else bH

# 138. 复制带随机指针的链表
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""
# O(1) 的空间复杂度
class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        map = {}
        cur = head
        while cur :
            map[cur] = Node(cur.val)
            cur = cur.next
        cur = head
        while cur :
            map[cur].next = map[cur.next] if cur.next else None
            map[cur].random = map[cur.random] if cur.random else None
            cur = cur.next
        return map[head] if head else None

    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head : return None
        cur = head
        next = None
        # copy node and link to every node
        while cur :
            next = cur.next
            cur.next = Node(cur.val)
            cur.next.next = next
            cur = next
        cur = head
        curCopy = None
        #  set copy node rand
        while cur :
            next = cur.next.next  # 一次移动两个点
            curCopy = cur.next
            curCopy.random = cur.random.next if cur.random else None
            cur = next
        res = head.next
        cur = head
        # set copy node next or named split
        while cur :
            next = cur.next.next
            curCopy = cur.next
            curCopy.next = next.next if next else None
            cur = next
        return res